package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 */
//给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 
//
// 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列
//，而 "AEC" 不是） 
//
// 题目数据保证答案符合 32 位带符号整数范围。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "rabbbit", t = "rabbit"
//输出：3
//解释：
//如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
//rabbbit
//rabbbit
//rabbbit 
//
// 示例 2： 
//
// 
//输入：s = "babgbag", t = "bag"
//输出：5
//解释：
//如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length, t.length <= 1000 
// s 和 t 由英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 864 👎 0

public class 不同的子序列{
	public static void main(String[] args) {
		Solution solution = new 不同的子序列().new Solution();
		String s = "rabbbit", t = "rabbit";
//		String s = "babgbag", t = "bag";

		solution.numDistinct(s,t);
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 *       j
	 *        r a b b b i t
	 *    i   0 1 2 3 4 5 6
	 *  r 0   1 1 1 1 1 1 1
	 *  a 1   0 1 1 1 1 1 1
	 *  b 2   0 0 1 2 3 3 3
	 *  b 3   0 0 0 1 3 3 3
	 *  i 4   0 0 0 0 0 3 3
	 *  t 5   0 0 0 0 0 0 3
	 *  初始化： 前j个子序列中 构成 前i个子序列的个数
	 *   第一列初始化为 1
	 *   if s[i] = t[j]
	 *  	 dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
	 *   else
	 *   	 dp[i][j] = dp[i][j-1]
	 */
    public int numDistinct(String s, String t) {

		int [][] dp = new int[t.length()+1][s.length()+1];
		for (int i = 0; i < s.length()+1; i++) {
//			if (s.charAt(0)==t.charAt(0)){
			dp[0][i] = 1;
//			}
		}
//    	dp[0][0] = s.charAt(0)==t.charAt(0)?1:0;  j 0  6  1  7

		for (int i = 1; i < t.length()+1; i++) {
			for (int j = 1; j < s.length()+1; j++) {
				if (s.charAt(j-1)==t.charAt(i-1)){
					dp[i][j] = dp[i][j-1]+dp[i-1][j-1];
				}else{
					dp[i][j] = dp[i][j-1];
				}
			}
		}

//		for (int i = 0; i < t.length(); i++) {
//			for (int j = 0; j < s.length(); j++) {
//				if (s.charAt(j)==t.charAt(i)){
//					dp[i+1][j+1] = dp[i+1][j]+dp[i][j];
//				}else{
////					dp[i+1][j+1] = dp[i+1][j];
//					dp[i+1][j+1] = dp[i+1][j];
//				}
//			}
//		}
		for (int i = 0; i < t.length()+1; i++) {
			for (int j = 0; j < s.length()+1; j++) {
				System.out.print(dp[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println(dp[t.length()][s.length()]);
		return dp[t.length()][s.length()];

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
